Print immutable linked list in reverse¶
Time: O(N); Space: O(SQRT(N)); medium
You are given an immutable linked list, print out all values of each node in reverse with the help of the following interface:
ImmutableListNode: An interface of immutable linked list, you are given the head of the list.
You need to use the following functions to access the linked list (you can’t access the ImmutableListNode directly):
ImmutableListNode.printValue(): Print value of the current node. ImmutableListNode.getNext(): Return the next node.
The input is only given to initialize the linked list internally. You must solve this problem without modifying the linked list. In other words, you must operate the linked list using only the mentioned APIs.
Example 1:
Input: head = {ImmutableListNode} 1->2->3->4->None
Output: {ImmutableListNode} 4->3->2->1->None
Example 2:
Input: head = {ImmutableListNode} 0->-4->-1->3->-5->None
Output: {ImmutableListNode} -5->3->-1->-4->0->None
Example 3:
Input: head = {ImmutableListNode} [-2,0,6,4,4,-6]
Output: {ImmutableListNode} [-6,4,4,6,0,-2]
Constraints:
The length of the linked list is between [1, 1000].
The value of each node in the linked list is between [-1000, 1000].
Follow up:
Could you solve this problem in:
Constant space complexity?
Linear time complexity and less than linear space complexity?
[29]:
class ImmutableListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def printValue(self):
print(self.val, end = '->')
def getNext(self):
return self.next
1. Use backets¶
[30]:
import math
class Solution1(object):
"""
Time: O(N)
Space: O(SQRT(N))
"""
def printLinkedListInReverse(self, head):
"""
:type head: ImmutableListNode
:rtype: None
"""
def print_nodes(head, count):
nodes = []
while head and len(nodes) != count:
nodes.append(head)
head = head.getNext()
for node in reversed(nodes):
node.printValue()
count = 0
curr = head
while curr:
curr = curr.getNext()
count += 1
bucket_count = int(math.ceil(count**0.5))
buckets = []
count = 0
curr = head
while curr:
if count % bucket_count == 0:
buckets.append(curr)
curr = curr.getNext()
count += 1
for node in reversed(buckets):
print_nodes(node, bucket_count)
[31]:
s = Solution1()
head = ImmutableListNode(1)
head.next = ImmutableListNode(2)
head.next.next = ImmutableListNode(3)
head.next.next.next = ImmutableListNode(4)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(0)
head.next = ImmutableListNode(-4)
head.next.next = ImmutableListNode(-1)
head.next.next.next = ImmutableListNode(3)
head.next.next.next.next = ImmutableListNode(-5)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(-2)
head.next = ImmutableListNode(0)
head.next.next = ImmutableListNode(6)
head.next.next.next = ImmutableListNode(4)
head.next.next.next.next = ImmutableListNode(4)
head.next.next.next.next.next = ImmutableListNode(-6)
s.printLinkedListInReverse(head)
4->3->2->1->
-5->3->-1->-4->0->
-6->4->4->6->0->-2->
2. Hash table¶
[32]:
class Solution2(object):
def printLinkedListInReverse(self, head):
"""
:type head: ImmutableListNode
:rtype: None
"""
nodes = []
while head:
nodes.append(head)
head = head.getNext()
for node in reversed(nodes):
node.printValue()
[33]:
s = Solution2()
head = ImmutableListNode(1)
head.next = ImmutableListNode(2)
head.next.next = ImmutableListNode(3)
head.next.next.next = ImmutableListNode(4)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(0)
head.next = ImmutableListNode(-4)
head.next.next = ImmutableListNode(-1)
head.next.next.next = ImmutableListNode(3)
head.next.next.next.next = ImmutableListNode(-5)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(-2)
head.next = ImmutableListNode(0)
head.next.next = ImmutableListNode(6)
head.next.next.next = ImmutableListNode(4)
head.next.next.next.next = ImmutableListNode(4)
head.next.next.next.next.next = ImmutableListNode(-6)
s.printLinkedListInReverse(head)
4->3->2->1->
-5->3->-1->-4->0->
-6->4->4->6->0->-2->
3. Two pointers¶
[34]:
class Solution3(object):
def printLinkedListInReverse(self, head):
"""
:type head: ImmutableListNode
:rtype: None
"""
tail = None
while head != tail:
curr = head
while curr.getNext() != tail:
curr = curr.getNext()
curr.printValue()
tail = curr
[35]:
s = Solution3()
head = ImmutableListNode(1)
head.next = ImmutableListNode(2)
head.next.next = ImmutableListNode(3)
head.next.next.next = ImmutableListNode(4)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(0)
head.next = ImmutableListNode(-4)
head.next.next = ImmutableListNode(-1)
head.next.next.next = ImmutableListNode(3)
head.next.next.next.next = ImmutableListNode(-5)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(-2)
head.next = ImmutableListNode(0)
head.next.next = ImmutableListNode(6)
head.next.next.next = ImmutableListNode(4)
head.next.next.next.next = ImmutableListNode(4)
head.next.next.next.next.next = ImmutableListNode(-6)
s.printLinkedListInReverse(head)
4->3->2->1->
-5->3->-1->-4->0->
-6->4->4->6->0->-2->
4. Recursion¶
[36]:
class Solution4(object):
def printLinkedListInReverse(self, head):
"""
:type head: ImmutableListNode
:rtype: None
"""
if not head:
return
self.printLinkedListInReverse(head.getNext())
head.printValue()
[37]:
s = Solution4()
head = ImmutableListNode(1)
head.next = ImmutableListNode(2)
head.next.next = ImmutableListNode(3)
head.next.next.next = ImmutableListNode(4)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(0)
head.next = ImmutableListNode(-4)
head.next.next = ImmutableListNode(-1)
head.next.next.next = ImmutableListNode(3)
head.next.next.next.next = ImmutableListNode(-5)
s.printLinkedListInReverse(head)
print()
head = ImmutableListNode(-2)
head.next = ImmutableListNode(0)
head.next.next = ImmutableListNode(6)
head.next.next.next = ImmutableListNode(4)
head.next.next.next.next = ImmutableListNode(4)
head.next.next.next.next.next = ImmutableListNode(-6)
s.printLinkedListInReverse(head)
4->3->2->1->
-5->3->-1->-4->0->
-6->4->4->6->0->-2->